\documentclass[10pt,a4paper]{report}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\author{Joel Howard, Kevin Johnson}
\title{Multiagent Lab}
\begin{document}
\maketitle
\section*{Introduction}
In the last lab, we were tasked to implement several search techniques to find paths (often optimal) given a graph representation of the Bzrflag world.  Though fairly contrived, it was an excellent building block in developing a path finding and following algorithm.  The point of this lab was to do just that.  The task of this lab was to design agents that find and follow a path to the enemy base, decoy and destroy the enemy tanks, and return with the captured flag all implemented with a finite state machine under the hood.  The following sections outline our implementation, the results of our demonstration, and ideas we have for improving out algorithm.

\section*{The Finite State Machine} 
In order to coordinate our tanks movements we used a finite state machine to transition the tanks from searching the maze into their roles of distracting and eliminating the enemy tanks. We employed the state pattern to allow our code to remain concise and easy to read and maintain. The finite state machine pictured in figure 1 illustrates how the transitions are made, while the discussion of each individual state will be discussed below.

\subsection*{FollowSearchPathState}
During this state the tanks follow an optimal path between the start and ending points. This path is determined using an A* search through the graph representing the world. During the initial movement toward the enemy flag the tanks are always asking if they have gotten to the danger threshold. This is the minimum radius from the enemy tanks where the tanks are safe from enemy fire. At this point they transition into the AssignDecoyOrSniperState.

\subsection*{AssignDecoyOrSniperState}
This state makes a decision about which tank will be assigned as the decoy, and which tank will be assigned to be the sniper. Both tanks will enter this state, but depending on the decision made in this state the tanks will diverge into two distinct paths of execution.

\subsection*{MoveToDecoyPrePositionState}
When a tank is assigned to be the decoy it transitions to this state. During this state the decoy tank follows an attractive field to the point determined to be the pre position point. Once the decoy has begun to move into pre position a flag is set that tells the sniper tank that he his free to begin his move into position. Once the decoy has reached his pre position he transitions into the DecoyEvasiveManeuverState.

\subsection*{MoveSniperIntoPositionState}
Once the sniper receives the signal from the decoy, the sniper follows an attract field to his sniping location. As soon as the sniper is in position he transitions to the SniperAssasinateTanksState.

\subsection*{DecoyEvasiveManeuverState}
During this state the tank makes a figure 8 in an attempt to draw enemy fire away from the sniper. This movement is modelled by transitioning between 4 sub states. These are DecoyHeadNorthState, DecoyHeadEastState, DecoyHeadSouthState, and DecoyHeadWestState. By transitioning between these states and following their attract fields the decoy is able to draw enemy fire long enough for the sniper to take out all the enemies. The decoy will hold this pattern until it receives word from the sniper that it is safe to capture the enemy flag.

\subsection*{SniperAssasinateTanksState}
Once the sniper is in position he immediately takes aim and tries to kill the enemy tanks. Using an attract field, but ignoring the speed element, the sniper aims at the target and fires. Once all the enemy tanks have been eliminated he sends a signal to the decoy that it is safe to capture the flag.

\subsection*{CaptureFlagState}
Once the enemies are no longer a threat, the decoy follows an attract field to the enemy flag. Once he has the flag safely in hand, both the sniper and the decoy transition back to the FollowSearchPathState. This time the destination is the home base.

\begin{figure*}
\includegraphics[width=120mm]{./Figures/FiniteStateMachine.pdf}
\caption{Finite State Machine controlling tank movement}
\label{StateMachine}
\end{figure*}

\section*{Path Planning}
For our given task, we needed to be able to get from our base to our enemy base and back in a reasonable and intelligent manner. The first step to accomplish this is to plan the desired path. This is, of course, easier said than done but, given our previous lab, proved to be fairly straight forward.  The following subsections outline how we built and searched our graphs.
\subsection*{Building the Graph}
Being able to produce a graph from a bzrflag world is essential to plan paths.  In the previous lab we had access to the occgrid command which provided us a graph of nodes that are either occupied or not.  It was up to us to determine edges, weights, etc.  For this lab, we decided to model our graphs in a similar fashion.  Each node of our graph represents a $MxM$ square of the world where $M$ is a distance in meters.  Thus we discritize the world into a $NxN$ graph where $N$ is equal to the width/height of the world over $M$.  We then establish edges between the nodes where the weight of those edges are equal to the distance between the center of the neighbouring nodes (discritized square).  It should be noted that we use an eight connected neighbourhood instead of a four connected one.  Thus not all the edges' weights are equal, i.e. diagonal edges are weighted more heavily than straight edges.

The second thing to note here is edges are not established to or from nodes that are occupied with an obstacle and are thus orphaned from the graph.  This comes from the fact that tanks cannot drive through or over obstacles.  Thus when searching the graph, outlined in the next section, we do not even consider nodes that are occupied by an obstacle.  This improves the searching as well as space requirements.  It should be stated that for optimal paths we do keep track of which nodes are next to obstacles and weight edges to them more severely.  This allows us to find a fairly short path to the goal while keeping a reasonable distance from the obstacle.

The last thing to note is how we determine if a node is "occupied" by an obstacle.  This is simply accomplished by building a bounding box for each obstacle in the world.  The bounding boxes are defined by the points which define the obstacle.  A node is occupied if its center is within at least one (often only one) of the bounding boxes.  Though not the most accurate for more complex obstacles, i.e. rotated squares, this method proves fairly effective for the maze worlds.
\subsection*{Searching the Graph}
Once we had a graph that represented the bzrflag world, searching the space proved fairly simple.  We decided, for the time and space complexity, to implement our searching using A*.  A* is a really fast search algorithm that provides optimal paths given an admissible heuristic.  Our heuristic was simply the euclidean distance from the current node's center to the goal node's center.  The the heuristic never overestimated the remaining path from a given node to the goal given the shortest distance between two points is a line.  Thus our heuristic was admissible and thus A* gave an optimal path.  It should be noted that  the paths are recomputed each time the FollowSearchPath state is reached.

Figure 2 is a visualization of the graph and the path found from a tank to the enemy flag.  Each square grid represents a node in the graph.  Figure 3 is a zoomed in version of the figure 2.
\section*{Following the Path}
This would seem like an excellent time to define what exactly a `path' is.  For our implementation the `path' provided by our implementation of A* is simply a vector of points in the world that when followed sequentially lead to the desired goal.  One of the challenges of this project was to get the tanks to follow that path.  The following sections outline how we implemented this idea using potential fields with a few tweaks.

\subsection*{Paths and Potential Fields}
The first (and really final) idea we implemented to have our tanks follow the given paths was to use attractor fields.  We defined an attractor field for each of the points along the path.  Of course, the fields alone did not guide the tank to the goal, especially if they all affect the tank at the same time.  To solve this problem we limited the attractor fields to only influence the tank one at a time in sequential order.  Thus the first attractor field draws the tank to the first point in the path until it gets within some distance of the point.  Then, when that distance threshold is met, the next attractor field takes over and the previous field does not influence the tank any more.  This way the tank is drawn from one point to the next until it reaches the goal.

\subsection*{A Better Way}
Though simply stepping though attractor fields proved effective the tanks still exhibited less than ideal behaviour. This included waving back and forth along the path, i.e. over correcting when slightly off the path, and turning completely around to reach a point when it would make more sense to move on to the next point.  The following sections outline how we corrected this behaviour.

\subsubsection*{Smoothing the Movement}
The first problem we tackled was getting the tanks moving in a smooth and intelligent manner.  The waving was caused by the waypoints (attractor fields) being too close together.  When the tank was slightly off the path it would turn sharply trying to get to the current waypoint, hitting it at a less than ideal angle.  Then, to hit the next way point, it would have to turn to correct its trajectory also hitting that waypoint at an odd angle.  Thus the tank waves from one waypoint to the next.

To correct this behaviour, instead of setting the waypoints at each point in the path, we set the waypoints to points where the tank would need to turn.  Given a list of points, you can define a series of vectors which define the movement (direction and magnitude) necessary to traverse the path.  To find points where the tank needed to turn was simply a matter of combining the vectors that had the exact same direction and assigning waypoints where the vectors' (looking forward and backward) directions did not match.  This way the waypoints are further apart and at points in the path where the approach angle is less important (i.e. the tanks is turning any ways).

\subsubsection*{Avoiding being Turned Around}
The other problem we had to deal with was tanks turning completely around when following the path.  This was caused by the tank  passing a point but not passing within the threshold distance, i.e. taking a wide turn around a point.  This was a little more tricky to solve.  In simple terms we defined a function which limited the influence of the attractor field to what we called a cone of influence.  The function we used is as follows:
\begin{equation}
I =
\left\{
	\begin{array}{ll}
		true & \mbox{if } \vec{T} \cdot \vec{P} \geq 0 \mbox{ and } abs( \theta_{\vec{T}} - \theta_{\vec{P}}) <= 45\deg\\
		true & \mbox{if } |\vec{T}| \leq d \\
		false & \mbox{otherwise} 
	\end{array}
\right.
\end{equation}
Where $I$ is a boolean defining if the tank has left the cone of influence, $\vec{T}$ is the vector defined by the tank location and the waypoint, $\vec{P}$ is the vector defined by the previous waypoint and the current waypoint, $\theta_{\vec{x}}$ is the direction or angle of some vector x, and $d$ is simply the distance threshold.  Thus the tank was in the influence of the attractor field if and only if the tank was outside the distance threshold and the angle between the tank and the waypoint was less than forty five degrees.  If the tank was outside the waypoint's influence then we simply moved to the next waypoint.  This proved quite effective given how we smoothed the movement.

\section*{Future Improvements}
There are several areas where we could improve upon our current implementation. One area where we could improve is in our definition of whether a node in the graph is occupied or not. Currently we use a bounding box around the points defined by the obstacle. While this works well for rectangular objects, it may not work for more complicated obstacles.

There are also several areas where we could improve the performance of our algorithms. We have noticed that there is a noticeable lag when we do a new search. If we were able to offload the search to a different thread so that we could maintain communication with our tank while we are calculating the next search path we would not have those moments where our tanks seem to be confused about what to do.

We have also identified another area where we could optimize the network traffic to get more throughput. We currently update our concept of the world, and then calculate and send all tank commands. It would be more optimal if we sent all of our network traffic in one burst, rather than in the two bursts that we currently have.

We explored the idea of assigning different roles to tanks in this lab. However, much of the behaviour is still hard coded. This is particularly true in the definition of the way points during evasive maneuvers, as well as the sniper's path. We could improve our logic to dynamically pick way points and sniping positions using information about the other tanks to increase our likelihood of not getting shot.

\section*{Results/Demonstrations}
The group that we demonstrated our code to, and subsequently demonstrated their code to us, was Samuel and Zach.  It was a good experience to watch their code run and to explain how we implemented our solution.  It was especially heartening to see that they struggled with the same problems we struggled with (though they found other solutions).

Seeing their implementation also showed us that there were other ways to approach both building and following the graph.  The other team still built their graphs with 1 meter blocks but down sampled the path.  This proved to give similar results to the larger granularity of our graphs.  The other team also still had waving issues, but did not feel it necessary to correct them.  We have to admit this did not adversely affect them as we figured it would.  All in all it was a good experience.

\begin{figure*}[h]
\includegraphics[width=120mm]{./Figures/FullGrid.png}
\caption{Visualization of graph generated from bzrflag maze world with computed path in blue.  Each grid block represents a node in the graph.}
\label{FullGrid}
\end{figure*}

\begin{figure*}[h]
\includegraphics[width=120mm]{./Figures/zoomedIn2.png}
\caption{Zoomed in version of figure 2.}
\label{ZoomedIn}
\end{figure*}

\end{document}